using System;

namespace DeflateLib
{
    /// <summary>
    /// 3-byte hash that was described in DEFLATE algorithm.
    /// </summary>
	sealed class LZ773ByteHash
	{
        const int ResetPositionAfter = 0x1000000;
        const int HashTableEntriesCount = 256;
		const ushort EmptyBag = 0xFFFF;
		const ushort EndOfChain = 0;

		int hashLength;
		ushort[] hashChains;
		int[] hashTable;
		int currentPosition;
		
		internal LZ773ByteHash(int size)
		{
			this.hashLength = size;
			this.hashChains = new ushort[hashLength];
			this.hashTable = new int[HashTableEntriesCount];
			this.currentPosition = 0;
			for(int i = 0; i < HashTableEntriesCount; i++)
			{
				this.hashTable[i] = EmptyBag;
			}		
		}
		
		internal void Clear()
		{
			this.currentPosition = 0;
			for(int i = 0; i < HashTableEntriesCount; i++)
			{
				this.hashTable[i] = EmptyBag;
			}		
		}
		
        /// <summary>
        /// Returns iterator for same tree byte hash, or null.
        /// </summary>
        /// <param name="data">data</param>
        /// <param name="offset">offset in data</param>
        /// <returns>iterator or null</returns>
		internal Iterator Get(byte[] data, int offset)
		{
			int hashCode = GetHashcode(data, offset);
			if(hashTable[hashCode] == EmptyBag || 
				currentPosition - hashTable[hashCode] > hashLength)
			{				
				return null;
			}
			else
			{
				return new Iterator(this, currentPosition - hashTable[hashCode]);
			}
		}

		internal void Push(byte[] data, int offset)
		{
			int hashCode = GetHashcode(data, offset);
			int index = currentPosition % hashLength;
			if(hashTable[hashCode] == EmptyBag || 
				currentPosition - hashTable[hashCode] >= hashLength)
			{
				hashChains[index] = EndOfChain;
			}
			else
			{				
				hashChains[index] = (ushort)(currentPosition - hashTable[hashCode]);
			}
			hashTable[hashCode] = currentPosition;
            if (++currentPosition >= ResetPositionAfter)
            {
                // shift if current position too big
                int shiftBy = currentPosition - hashLength;
                shiftBy -= shiftBy % hashLength;
                for (int i = 0; i < hashTable.Length; i++)
                {
                    if (hashTable[i] >= shiftBy)
                        hashTable[i] -= shiftBy;
                    else
                        hashTable[i] = EndOfChain;
                }
                currentPosition -= shiftBy;
            }
		}

		internal void Push(byte[] data, int offset, int length)
		{
			for(int i=0; i < length; i++)
				Push(data, offset + i);
		}
		
		internal void Skip(int length)
		{
            System.Diagnostics.Debug.Assert(length >= 0);

			currentPosition += length;
		}
		
		private static int GetHashcode(byte[] data, int offset)
		{
			return (byte)(data[offset] + data[offset + 1] + data[offset + 2]);
		}
		
		internal sealed class Iterator
		{
			LZ773ByteHash owner;
			int distance;
			int state = 0;
			
			internal int CurrentDistance
			{
				get { return distance; }
			}
			
			internal Iterator(LZ773ByteHash owner, int distance)
			{
				this.owner = owner;
				this.distance = distance;
			}
			
			internal bool MoveNext()
			{
				switch(state)
				{
					case 0:
						state = 1;
						return true;
					case 1:
						int index = (owner.currentPosition - distance) % owner.hashLength;
						ushort offset = owner.hashChains[index];
						if(offset == EndOfChain)
						{
							state = 2;
							return false;
						}
						else
						{
							distance += offset;
							if(distance > owner.hashLength)
							{
								state = 2;
								return false;
							}
							else
								return true;
						}
					default:
					case 2:
						return false;
				}
			}
		}
	}
}
